//
// Created by xili on 2024/9/10 9:39.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int maxSatisfaction(vector<int> &satisfaction) {
        sort(satisfaction.rbegin(), satisfaction.rend());
        int f = 0; // f(0) = 0
        int s = 0; // satisfaction 的前缀和
        for (int x: satisfaction) {
            s += x;
            if (s <= 0) { // 后面不可能找到更大的 f(k)
                break;
            }
            f += s; // f(k) = f(k-1) + s
        }
        return f;
    }
};